


# 辅助函数：用于对匹配字符串统计其Next列表：
def KMPpreprocess(p):
    nxt = []
    nxt.append(0)  # next[0]必然为零
    x = 1
    now = 0

    while x < len(p):
        if p[now] == p[x]:  # 如果p[now] == p[x]，则可以向右扩展一位
            now += 1
            x += 1
            nxt.append(now)
        elif now:
            now = nxt[now - 1]  # 缩小now，改成nxt[now - 1]

        else:
            nxt.append(0)  # now已经为0，无法缩小，直接让next[now] = 0
            x += 1
    return nxt


# 主函数，寻找公共子串：
def KMPsearch(s, p):
    tar = 0
    pos = 0

    nxt = KMPpreprocess(p)  # 调用子函数，预处理模版字符串
    print(f"next列表为：{nxt}")

    while tar < len(s):
        if s[tar] == p[pos]:  # 成功匹配，进入下一个字符判断
            tar += 1
            pos += 1
        elif pos:  # 匹配失败，找下一个起始点
            pos = nxt[pos - 1]
        else:      # 没有起始点就直接从头开始
            tar += 1

        if pos == len(p):   # 完成匹配
            print(tar - pos + 1)
            pos = nxt[pos - 1]  # 可能需要找到所有匹配子串


if __name__ == "__main__":
    # s = input("请输入被匹配字符串：").strip()  # 输入被匹配字符串
    # p = input("请输入想要寻找字符串：").strip()  # 输入匹配模版
    s = 'aabaaabababaa'
    p = 'abaa'

    KMPsearch(s, p)


